#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 如果目标值存在返回下标，否则返回 -1
# @param nums int整型一维数组
# @param target int整型
# @return int整型
#
class Solution:
    def search(self, nums, target):
        # write code here
        if len(nums) == 0:
            return -1

        left = 0
        right = len(nums) - 1
        ans = -1  # default case for no answer found
        while left <= right:  # for overlapping
            mid = (left + right) // 2  # 右移左指针会移动mid, 而且每次只移动一个，这样只会使mid也只向右移动一个！
            if nums[mid] == target:
                ans = mid  # 记录答案防止之后相同的数字
                right = mid - 1
            elif nums[mid] < target:
                # 小了，得右移
                left = mid + 1
            elif nums[mid] > target:
                # 大了，得左移
                right = mid - 1
        return ans


nums = [2, 3, 6, 7, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 10, 12, 12, 12, 15, 16, 17, 17, 18, 18, 19, 20, 21, 26, 27, 27, 28,
        29, 30, 30, 31, 32, 33, 33, 34, 36, 36, 37, 37, 38, 38, 40, 40, 41, 41, 41, 41, 42, 43, 43, 44, 45, 47, 49, 50,
        51, 52, 52, 53, 54, 54, 54, 55, 55, 56, 56, 58, 58, 59, 59, 61, 62, 62, 64, 65, 65, 66, 67, 69, 69, 70, 71, 73,
        75, 77, 78, 78, 78, 85, 85, 86, 88, 88, 88, 89, 90, 91, 91, 94, 94, 94, 96, 97, 97, 99, 101, 102, 103, 106, 107,
        109, 111, 113, 114, 115, 116, 118, 119, 119, 120, 121, 121, 123, 124, 124, 124, 126, 127, 127, 128, 128, 129,
        130, 130, 131, 131, 131, 132, 132, 133, 133, 134, 134, 135, 136, 137, 138, 139, 139, 140, 141, 142, 143, 143,
        143, 144, 144, 145, 145, 147, 149, 150, 151, 152, 152, 153, 154, 155, 155, 158, 158, 159, 162, 162, 163, 164,
        165, 166, 167, 167, 167, 168, 168, 170, 171, 173, 173, 174, 177, 178, 178, 179, 179, 179, 180, 185, 187, 187,
        187, 188, 188, 188, 189, 189, 191, 193, 193, 193, 195, 195, 196, 201, 202, 202, 203, 204, 204, 207, 207, 209,
        209, 210, 210, 212, 212, 212, 213, 213, 214, 217, 219, 221, 224, 224, 226, 226, 227, 227, 228, 228, 231, 231,
        234, 235, 236, 236, 237, 237, 238, 239, 240, 244, 245, 246, 246, 250, 250, 251, 252, 253, 256, 257, 258, 258,
        261, 262, 263, 265, 266, 266, 268, 270, 270, 271, 273, 274, 274, 275, 277, 278, 278, 278, 282, 284, 284, 285,
        285, 292, 294, 295, 296, 296, 298, 299, 301, 303, 305, 306, 309, 311, 312, 314, 314, 315, 315, 315, 318, 320,
        320, 320, 320, 323, 324, 324, 325, 325, 327, 328, 329, 329, 329, 329, 330, 330, 330, 330, 330, 331, 331, 334,
        334, 335, 335, 339, 339, 340, 340, 341, 341, 344, 346, 346, 346, 348, 348, 349, 349, 350, 350, 350, 351, 351,
        352, 352, 354, 355, 356, 357, 362, 362, 363, 363, 364, 366, 366, 366, 367, 369, 369, 369, 370, 371, 371, 372,
        373, 375, 376, 376, 378, 379, 380, 381, 383, 384, 384, 385, 385, 385, 388, 388, 390, 392, 393, 393, 393, 394,
        395, 395, 396, 396, 398, 398, 398, 399, 400, 401, 404, 405, 405, 406, 406, 406, 407, 407, 407, 408, 408, 410,
        410, 411, 413, 414, 414, 415, 419, 420, 422, 425, 426, 426, 431, 431, 433, 433, 433, 433, 434, 435, 436, 436,
        438, 439, 440, 440, 441, 444, 446, 446, 446, 447, 447, 447, 448, 448, 448, 453, 454, 454, 455, 456, 456, 457,
        460, 463, 464, 464, 469, 470, 471, 471, 474, 475, 475, 479, 482, 482, 482, 483, 484, 486, 486, 487, 487, 489,
        489, 491, 492, 495, 496, 496, 496, 498, 498, 499, 499, 500, 503, 503, 505, 505, 507, 508, 508, 508, 510, 513,
        514, 517, 519, 520, 522, 522, 522, 522, 523, 524, 524, 525, 527, 528, 528, 529, 530, 532, 534, 535, 53]
target = 9
s = Solution()
idx = s.search(nums, target)
print(idx)
